/**
 * 实现 strStr() 函数。
 * <p>
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 * <p>
 * 示例 1:
 * <p>
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 */
class Scratch {

    public static void main(String[] args) {
        // System.out.println(strStr("hello", "ll"));
        System.out.println(strStr("aaa", "a"));
    }


    /**
     * 使用字符串数组会比charAt快，使用对象记录会比每次去拿要快
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {
        if (null == haystack || null == needle) return -1;
        if (haystack.equals(needle) || needle.length() == 0) return 0;
        char first = needle.charAt(0);
        int max = haystack.length() - needle.length();
        char[] source = haystack.toCharArray();
        char[] target = needle.toCharArray();
        for (int i = 0; i <= max; i++) {
            // 找到第一个
            if (source[i] != first) continue;
            //找到之后判断余下
            if (target.length == 1) return i;
            for (int x = 1; x < target.length; i++, x++) {
                if (source[i + 1] == target[x]) {
                    if (x == target.length - 1) {
                        return i - x + 1;
                    }
                } else {
                    i = i - x + 1;
                    break;
                }
            }
        }
        return -1;
    }

    public static int strStr2(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}